package org.example.struct.array2;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author liyishan
 * @date 2023/10/20 10:50
 * @apiNote
 */

public class Test00907SumSubarrayMins {


    public static void main(String[] args) {

    }

    public static int test(int[] arr) {
        int n = arr.length;
        Deque<Integer> monoStack = new ArrayDeque<>();
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 0; i < n; i++) {
            while (!monoStack.isEmpty() && arr[i] <= arr[monoStack.peek()]) {
                monoStack.pop();
            }
            left[i] = i - (monoStack.isEmpty() ? -1 : monoStack.peek());
            monoStack.push(i);
        }
        monoStack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!monoStack.isEmpty() && arr[i] < arr[monoStack.peek()]) {
                monoStack.pop();
            }
            right[i] = (monoStack.isEmpty() ? n : monoStack.peek()) - i;
            monoStack.push(i);
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans = (ans + (long) left[i] * right[i] * arr[i]) % 1000000007;
        }
        return (int) ans;
    }

    public static int test1(int[] arr) {
        int n = arr.length;
        long ans = 0;
        Deque<Integer> monoStack = new ArrayDeque<>();
        int[] dp = new int[n];
        for(int i = 0; i < n; i++){
            while(!monoStack.isEmpty() && arr[monoStack.peek()] >arr[i]){
                monoStack.pop();
            }
            int k = monoStack.isEmpty() ? (i+1):(i-monoStack.peek());
            dp[i] = k*arr[i] +(monoStack.isEmpty()?0:dp[i-k]);
            ans = (ans+dp[i])%1000000007;
            monoStack.push(i);
        }
        return (int) ans;
    }

}
